//
//  Offer_04.swift
//  LeetCode
//
//  Created by migu on 2020/9/8.
//  Copyright © 2020 LBB. All rights reserved.
//  剑指 Offer 04. 二维数组中的查找
//  在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//[
//  [1,   4,  7, 11, 15],
//  [2,   5,  8, 12, 19],
//  [3,   6,  9, 16, 22],
//  [10, 13, 14, 17, 24],
//  [18, 21, 23, 26, 30]
//]
//给定 target = 5，返回 true。
//
//给定 target = 20，返回 false。
//
//
//
//限制：
//
//0 <= n <= 1000
//
//0 <= m <= 1000

import Foundation

class FindNumberIn2DArray {
    func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
        //解法1
//        for i in 0..<matrix.count {
//            let array = matrix[i]
//            if array.contains(target) {
//                return true
//            }
//        }
//        return false
        if matrix.count == 0 {
            return false
        }
        var row = 0
        var cloum = matrix[row].count - 1
        while row < matrix.count && cloum >= 0 {
            let tempTarget = matrix[row][cloum]
            if tempTarget == target {
                return true
            } else if tempTarget < target {
                row += 1
            } else if tempTarget > target {
                cloum -= 1
            } else {}
        }
        
        return false
    }
}
